package com.mj.listen2._02_并查集;

/**
 * Quick Union - 基于rank的优化 - 路径分裂(Path Spliting)
 */
public class UnionFind_QU_R_PS extends UnionFind_QU_R {
    public UnionFind_QU_R_PS(int capacity) {
        super(capacity);
    }

    /**
     * 通过 parent 链条不断往上找祖父节点，直到找到根节点
     * 使路径
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            // 记录父节点
            int P = parents[v];
            // 让当前v节点指向祖父节点
            parents[v] = parents[P];
            // v 等于之前的父节点，因为父节点也要经历指向祖父节点的过程
            v = P;
        }
        return v;
    }
}
